// 分治 - 归并
// 归并的核心思路就是先将数组分左右两块
// 再把左边数组排序，右边数组排序
// 再合并两个有序数组
// 类似于二叉树的后续遍历

// 例题 1：
// 给你一个整数数组 nums，请你将该数组升序排列。
// 必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
//
//        示例 1：
//
//        输入：nums = [5,2,3,1]
//        输出：[1,2,3,5]
//        示例 2：
//
//        输入：nums = [5,1,1,2,0,0]
//        输出：[0,0,1,1,2,5]
//
//
//        提示：
//
//        1 <= nums.length <= 5 * 104
//        -5 * 104 <= nums[i] <= 5 * 104

// 解题思路:
// 数组分左右两块 - 递归排序
// 合并两个有序数组
// 还原数组

public class SortArray {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int start, int end){
        if(start >= end) return;
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        int n = end - start + 1;
        int[] tmp = new int[n];
        int left = start; int right = mid + 1;
        int i = 0;
        while(left <= mid && right <= end){
            if(nums[left] <= nums[right]) tmp[i++] = nums[left++];
            else tmp[i++] = nums[right++];
        }
        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= end) tmp[i++] = nums[right++];
        for(int k = 0; k < n; k++) nums[k + start] = tmp[k];
    }
}